In order to perform processing to high-speed packets (Gigabit Ether etc.), an attempt is made to increase the processing speed by using a plurality of processors for parallel processing. Moreover, load dispersion, higher-speed processing, and packet order matching among the plurality of processors are realized by using a token among the plurality of processors.
FIG. 15 shows a communication device of a multi-processor system according to a conventional technique. In the communication device, first to fourth processor units 1501 to 1504 are connected in parallel and a packet 1531 is inputted and a packet 1532 is outputted. The first processor unit 1501 comprises a first receiving processor 1511a, a first receiving buffer 1512a, and a first manipulating processor 1513a. The second processor unit 1502 comprises a second receiving processor 1511b, a second receiving buffer 1512b, and a second manipulating processor 1513b. The third processor unit 1503 comprises a third receiving processor 1511c, a third receiving buffer 1512c, and a third manipulating processor 1513c. The fourth processor unit 1504 comprises a fourth receiving processor 1511d, a fourth receiving buffer 1512d, and a fourth manipulating processor 1513d. 
Hereinafter, the individual or all of the first to fourth receiving processors 1511a to 1511d are referred to as a receiving processor 1511, the individual or all of the first to fourth receiving buffers 1512a to 1512d are referred to as a receiving buffer 1512, and the individual or all of the first to fourth manipulating processors 1513a to 1513d are referred to as a manipulating processor 1513.
The main function of the receiving processor 1511 is to receive packets. The main function of the manipulating processor 1513 is to manipulate the received packets and to transmit packets. The receiving buffer 1512 has an interface function between the receiving processor 1511 and the manipulating process 1513, and has a buffering capacity, for example, for two packets.
A reception token 1541 and a transmission token 1542 circulate through the processor units 1501 to 1504 asynchronously. Upon receipt of the reception token 1541, the receiving processor 1511 receives the reception packet 1531 and passes the reception token 1541 to the next process unit. Upon receipt of the transmission token 1542, the manipulating processor 1513 transmits the transmission packet 1532 and passes the transmission token 1542 to the next processor unit.
In the flow of the operation, when the packet 1531 is inputted, the receiving processor 1511 having the reception token 1541 receives the packet 1531 and the received packet is stored in the receiving buffer 1512. When learning that the packet is stored in the receiving buffer 1512, the manipulating processor 1513 starts to perform processing to the packet and, if having the transmission token 1542, transmits the packet and releases the receiving buffer 1512 when the processing is completed.
The flow described above is an ideal flow of processing but the above-mentioned processing is not necessarily performed because of the recent trend toward higher-speed communication and toward more complex incorporated functions. When a packet is inputted, the receiving buffer 1512 tries to receive the packet but, if an over-load is imposed such that the receiving buffer 1512 is not released before the packet is inputted because the manipulating processor 1513 is in a congestion state, the packet cannot be received. In other words, the packet is discarded as a result.
In a network processor etc., the manipulating processor 1513 is programmable and it is possible for a programmer to create an arbitrary program. As the scale of this program becomes larger, the processing time becomes longer, the release of the receiving buffer 1512 is delayed and the number of packets to be discarded increases. Due to the occurrence of the packet to be discarded, the order of the packets is reversed, which cannot be resolved by the packet order matching by a token. The operation at this time is shown below.
As shown in FIG. 16, when packets P1 to P8 are inputted successively, first, the first receiving processor 1511a having the reception token 1541 receives the packet P1, stores the packet in the first receiving buffer 1512a, and passes the reception token 1541 to the second receiving processor 1511b. Next, the receiving processor 1511b having the reception token 1541 receives the packet P2, stores the packet in the receiving buffer 1512b, and passes the reception token 1541 to the third receiving processor 1511c. After this, the reception token 1541 is circulated through the third receiving processor 1511c→the fourth receiving processor 1511d→the first receiving processor 1511a . . . , and thus the packets are received.
Due to this, the first receiving buffer 1512a stores the packets P1 and P5, the second receiving buffer 1512b stores the packets P2 and P6, the third receiving buffer 1512c stores the packets P3 and P7, and the fourth receiving buffer 1512d stores the packets P4 and P8. The first manipulating processor 1513a performs processing to the packet P1 in the first receiving buffer 1512a, the second manipulating processor 1513b performs processing to the packet P2 in the second receiving buffer 1512b, the third manipulating processor 1513c performs processing to the packet P3 in the third receiving buffer 1512c, and the fourth manipulating processor 1513d performs processing to the packet P4 in the fourth receiving buffer 1512d. 
Next, as shown in FIG. 17, since having the transmission token 1542, the first manipulating processor 1513a transmits the processed packet P1 and releases the packet P1 in the first receiving buffer 1512a. After this, the first manipulating processor 1513a passes the transmission token 1542 to the second manipulating processor 1513b and performs processing to the packet P5 in the first receiving buffer 1512a. 
After this, when packets P9 to P12 are inputted successively, the first receiving processor 1511a having the reception token 1541 receives the packet P9, stores the packet in the first receiving buffer 1512a, and passes the reception token 1541 to the second receiving processor 1511b. Next, the second receiving processor 1511b having the reception token 1541 receives the packet 10, but discards the packet P10 because the receiving buffer 1512b is full and passes the reception token 1541 to the third receiving processor 1511c. Similarly, the third and fourth receiving processors 1511c and 1511d discard the packets P11 and P12 because the receiving buffers 1512c and 1512d are full.
Next, as shown in FIG. 18, since having the transmission token 1542, the second manipulating processor 1513b transmits the processed packet P2 and releases the packet P2 in the second receiving buffer 1512b. After this, the second manipulating processor 1513b passes the transmission token 1542 to the third manipulating processor 1513c and performs processing to the packet P6 in the second receiving buffer 1512b. Similarly, the third and fourth manipulating processors 1513c and 1513d transmit the packet P3 and P4, respectively, and then perform processing to the packets P7 and P8. Next, the first manipulating processor 1513a transmits the packet P5 and then performs processing to the packet P9.
Next, when packets P13 to P16 are inputted successively, the first receiving processor 1511a having the reception token 1511 receives the packet P13, stores the packet in the first receiving buffer 1512a, and passes the reception token 1541 to the second receiving processor 1511b. Similarly, the second to fourth receiving processors 1511b to 1511d receive the packets P14 to P16, respectively, and store the packets in the receiving buffers 1512b to 1512d. 
Next, as shown in FIG. 19, since having the transmission token 1542, the second manipulating processor 1513b transmits the processed packet P6 and releases the packet P6 in the second receiving buffer 1512b. After this, the second manipulating processor 1513b performs processing to the packet P14 in the second receiving buffer 1512b. Similarly, the third and fourth manipulating processors 1513c and 1513d transmit the packets P7 and P8, respectively, and then perform processing to the packets P15 and P16. Next, the first manipulating processor 1513a transmits the packet P9 and then performs processing to the packet P13.
Next, as shown in FIG. 20, since having the transmission token 1542, the second manipulating processor 1513b transmits the processed packet P14 and releases the packet P14 in the second receiving buffer 1512b. Next, similarly, the third and fourth manipulating processors 1513c and 1513d transmit the packets P15 and P16, respectively. Next, the first manipulating processor 1513a transmits the packet P13.
As described above, the transmission token 1542 circulates and transmission is performed in the order of the first manipulating processor→the second manipulating processor→the third manipulating processor→the fourth manipulating processor→the first manipulating processor→ . . . . Since the packet itself does not have a number of identifying the input order, each manipulating processor 1513 cannot learn what number packet is that stored in the receiving buffer 1512 and processing is performed simply in order of storage in the receiving buffer 1512. Therefore, if the packets P10 to P12 are discarded, a problem arises in that the order of transmission of the packet P13 is reversed. That is, the order of the packets is P14→P15→P16→P13. In this case also, it is preferable for the packet P13 to be transmitted in the proper order.
If a packet is transmitted in reversed order, the packet cannot be received by a proper destination, resulting in an increase in unwanted traffic caused by its recovery. It is necessary to keep the influence on the processing performance of a processor to a minimum, therefore, it is required for a method for preventing the order of packets from being reversed to be simplified as much as possible.
Moreover, the following Patent document 1 is disclosed.
[Patent Document 1]
Japanese Patent Application Laid-Open No. Hei 9-162927